from mcp.server.fastmcp import FastMCP
from typing import Optional
import math

mcp = FastMCP("Modular Inverse Calculator")

@mcp.tool()
def modular_inverse(a: int, m: int) -> Optional[int]:
    """计算大数模逆运算
    
    Args:
        a: 需要求逆元的整数
        m: 模数
        
    Returns:
        返回a在模m下的逆元，如果不存在则返回None
    """
    try:
        # 处理边界情况
        if m <= 1:
            return None
            
        # 处理负数情况
        a = a % m
        
        # 检查是否互质
        if math.gcd(a, m) != 1:
            return None
            
        # 使用扩展欧几里得算法计算模逆
        def extended_gcd(a, b):
            if b == 0:
                return (a, 1, 0)
            else:
                # 使用迭代方式避免递归深度限制
                old_r, r = a, b
                old_s, s = 1, 0
                old_t, t = 0, 1
                
                while r != 0:
                    quotient = old_r // r
                    old_r, r = r, old_r - quotient * r
                    old_s, s = s, old_s - quotient * s
                    old_t, t = t, old_t - quotient * t
                
                return (old_r, old_s, old_t)
                
        g, x, _ = extended_gcd(a, m)
        if g != 1:
            return None
        else:
            result = x % m
            # 验证结果是否正确
            if (a * result) % m == 1:
                return result
            return None
            
    except Exception:
        return None

if __name__ == "__main__":
    mcp.run(transport="stdio")